package com.canopys.study.open.test.algorithm.threesum;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Stack;

/**
 * @Author: Canopys
 * @Descrption:
 * @Date: Created in 22:15 2020/5/13
 * @Modified By:
 */
public class ThreeSum {

    public static int findPro(int[] nums, int start, int end) {
        int base = nums[start];
        int j = end;
        for (int i = end; i > start; i--) {
            if (nums[i] > base) {
                int tmp = nums[i];
                nums[i] = nums[j];
                nums[j] = tmp;
                j--;
            }
        }
        nums[start] = nums[j];
        nums[j] = base;

        return j;
    }

    public static void quickSort(int[] nums, int start, int end) {
        if (start >= end) {
            return;
        }

        int p = findPro(nums, start, end);
        quickSort(nums, start, p - 1);
        quickSort(nums, p + 1, end);
        return;
    }

    public static int threeSumClosest(int[] nums, int target) {
        int length = nums.length;
        quickSort(nums, 0, length - 1);
        int min = nums[0] + nums[1] + nums[2];

        for (int i = 0; i < length - 2; i++) {
            int start = i + 1;
            int end = length - 1;
            while(end > start) {
                int sum = nums[i] + nums[start] + nums[end];

                if (Math.abs(target - min) > Math.abs(target - sum)) {
                    min = sum;
                }

                if (sum > target) {
                    end--;
                } else if (sum < target) {
                    start++;
                } else {
                    return sum;
                }
            }
        }

        return min;
    }

    public static Map<Character, List<String>> INIT_MAP = new HashMap<>();

    public static List<String> getLetter(String digits, int length) {
        if (length == 1) {
            return INIT_MAP.get(digits.charAt(0));
        }

        List<String> res = new ArrayList<>();
        List<String> list = INIT_MAP.get(digits.charAt(length - 1));
        for (String s : list) {
            for (String e : getLetter(digits, length - 1)) {
                res.add(e + s);
            }
        }
        return res;
    }

    public static int minIncrementForUnique(int[] A) {
        int[] count = new int[40000];
        for (int i = 0; i < A.length; i++) {
            count[A[i]]++;
        }

        int sum = 0;
        int rev = 0;
        for (int i = 0; i < 40000; i++) {
            if (count[i] == 0) {
                sum += rev;
                rev = (rev == 0 ? 0 : (rev - 1));
            } else if (count[i] == 1) {
                sum += rev;
            } else {
                sum += rev;
                rev = rev + count[i] - 1;
            }
        }

        while(rev > 0) {
            sum += rev;
            rev--;
        }

        return sum;
    }

    public static List<String> letterCombinations(String digits) {
        INIT_MAP.put('2', Arrays.asList("a", "b", "c"));
        INIT_MAP.put('3', Arrays.asList ("d", "e", "f"));
        INIT_MAP.put('4', Arrays.asList ("g", "h", "i"));
        INIT_MAP.put('5', Arrays.asList ("j", "k", "l"));
        INIT_MAP.put('6', Arrays.asList ("m", "n", "o"));
        INIT_MAP.put('7', Arrays.asList ("p", "q", "r", "s"));
        INIT_MAP.put('8', Arrays.asList ("t", "u", "v"));
        INIT_MAP.put('9', Arrays.asList ("w", "x", "y", "z"));

        return getLetter(digits, digits.length());
    }

    public static String countOfAtoms(String formula) {

        if (formula == null || formula.length() == 0) {
            return null;
        }

        Stack stack = new Stack();

        int index = formula.length() - 1;
        while(index < formula.length()) {
            Character c = formula.charAt(index);
            if ('(' == c) {

            }
        }

        return null;
    }

    public static void main(String[] args) {
        /*int[] nums = new int[] {-1, 2 ,1 ,-4};
        System.out.println(threeSumClosest(nums, 1));

        List<String> list = letterCombinations("234");
        System.out.println(list);*/

        int[] co = new int[] {1, 2, 2};
        //minIncrementForUnique(co);

        Map map = new HashMap();
        map.put("1", "1");

        Stack stack = new Stack();
        stack.push(map);

        map.clear();
        Map map1 = (Map) stack.pop();
        System.out.println(map1);


    }
}
